T. Kurahashi; "不完全性定理の数学的発展"
メモ
一階述語論理の言語$ \mathscr{L}を定める
具体的には
変数$ x,y,z,\dots
関係: $ =,\leqなど
2変数の関係記号$ =は必ず存在するとする
演算子: $ s,+,\times
定数: $ 0
量化子: $ \forall,\exists
$ \mathscr{L}の$ \mathscr{L}項及び論理式$ \mathscr{L}論理式を標準的な方法で定める．
以下は$ \mathscr{L}を省略する．
自由変数を含まない論理式は文と呼ぶ．
理論について
$ \mathscr{L}の文の集合を$ \mathscr{L}理論と呼ぶ．
理論$ Tについて，
$ T \vdash \varphi: $ Tで証明可能
論理式$ \varphiが，$ Tの要素と$ \mathscr{L}に関する公理及び推論規則で証明可能．
$ \text{Th}_T: $ Tの全ての定理集合
集合$ \text{Th}_T := \{ \varphi \mid T \vdash \varphi \}
$ Tが矛盾
$ T \vdash \varphiかつ$ T \vdash \lnot \varphiなる論理式$ \varphiが存在する．
$ Tが無矛盾
$ Tが無矛盾でない．
$ T \vdash \varphiかつ$ T \vdash \lnot \varphiなる論理式$ \varphiが存在しない．
「$ T \vdash \varphiまたは$ T \vdash \lnot \varphiのどちらかである」ではないことに注意．
それは$ Tの完全性である．
$ Tが完全
すべての文$ \varphiについて$ T \vdash \varphiまたは$ T \vdash \lnot \varphiのどちらか
モデルについて
$ \mathscr{L}の構造$ \mathcal{M} = \lang M,\xi \rangとは次で構成される
非空集合$ M
$ \mathscr{L}の各記号の解釈$ \xi（写像のように）
$ k項関係$ Rに対して$ R^\mathcal{M} \sube M^k（$ M上の$ k項関係）
すなわち，$ \llbracket R \rrbracket_\xi = R^\mathcal{M}
$ k項演算子$ fに対して$ f^\mathcal{M} \in (M^k \mapsto M)（$ M上の$ k項関数）
すなわち，$ \llbracket f \rrbracket_\xi = f^\mathcal{M}
定数$ cに対して$ c^\mathcal{M} \in M
すなわち，$ \llbracket c \rrbracket_\xi = c^M
用語
$ \mathcal{M} \models \varphi: 論理式$ \varphiは構造$ \mathcal{M}で妥当
$ \mathcal{M} \models T: 構造$ \mathcal{M}は理論$ Tのモデル
すべての$ Tの要素（すなわち文）$ \tauについて$ \mathcal{M} \models \tau
$ T \models \varphi: $ T恒真?
理論$ Tのすべてのモデル$ \mathcal{M}について$ \mathcal{M} \models \varphi
定理1: 一階述語論理の完全性定理
任意の理論$ T及び文$ \varphiについて，
$ T \vdash \varphi$ \iff$ T \models \varphi
直感的意味
$ \impliedby: 意味論的に妥当な文は全て証明できる．
一階の算術
算術の言語$ \mathscr{L}_A := \{ =, \leq, s, +, \times,\mathbf{0}\}
関係
$ =，2
$ \leq，2
演算子
$ s: 1
$ +: 2
$ \times: 2
定数記号
$ \mathbf{0}
$ \mathscr{L}_Aの標準構造$ \mathcal{N} = \lang \omega, \xi\rang $ \omega = \{0,1,2,\dots\}
$ =^\mathcal{N}: 等号
$ \leq^\mathcal{N}: 自然数上の線形順序
$ s^\mathcal{N}: 自然数上の後置関数
$ +^\mathcal{N}: 自然数上の加算
$ \times^\mathcal{N}: 自然数上の乗算
$ \mathbb{0}^\mathcal{N}: 自然数0
$ \Delta_n,\Sigma_n,\Pi_n関係
自然数$ nに対して，数項$ \overline{n}
量化子を含まない論理式は開論理式と呼ぶ．
量化が有界な論理式の略記法
論理式$ \varphiと，変数$ xを含まない項$ tについて，
$ \exists x \leq t. \varphi: $ \exists x.((x \leq t) \land \varphi)
$ \forall x \leq t. \varphi: $ \forall x.((x \leq t) \land \varphi)
$ \Delta_0論理式
開論理式$ \varphiに有界量化のみが行われた論理式を$ \Delta_0論理式
$ \Sigma_n論理式，$ \Pi_n論理式
$ \Delta_0論理式は$ \Sigma_0論理式または$ \Pi論理式でもある
$ 0 \leq kについて，
$ \Pi_n論理式$ \varphiについて普通の存在量化が行われた論理式は$ \Sigma_{n+1}論理式である．
すなわち，$ \exists v_0,\dots,\exists v_{k-1}. \varphi形の論理式が$ \Sigma_{n+1}論理式である
$ \Sigma_n論理式$ \varphiについて普通の全称量化が行われた論理式は$ \Pi_{n+1}論理式である．
すなわち，$ \forall v_0,\dots,\forall v_{k-1}. \varphiの形の論理式が$ \Pi_{n+1}論理式である
$ k=0でも成り立つ，すなわち
任意の$ \Sigma_n論理式は$ \Pi_{n+1}論理式である
任意の$ \Pi_n論理式は$ \Sigma_{n+1}論理式である
双対性
$ \Sigma_nと$ \Pi_nには双対性が成り立つ．
$ \Sigma_n論理式の否定は$ \Pi_n論理式である．
$ \Sigma_n^d = \Pi_n
$ \Pi_n論理式の否定は$ \Sigma_n論理式である．
$ \Pi^d_n = \Sigma_n
Skolem標準形より$ \mathscr{L}の任意の論理式は$ \Sigma_n論理式（$ nは任意の自然数）に帰着できる 理論の$ \Sigma_n健全性
理論$ Tが$ \Sigma_n健全である
$ Tにおいて証明可能な$ \Sigma_n文は全て$ \mathcal{N}で妥当である
$ T \vdash \varphi$ \implies$ \mathcal{N} \models \varphi．
ただし$ \varphiは$ \Sigma_n文とする
補題1: $ \Sigma_n健全性と無矛盾性
$ \Sigma_n健全な理論$ Tは無矛盾性を満たす．
すなわち，$ \Sigma_n健全性は無矛盾性より強い性質/要請である．
理論の健全性
理論$ Tが健全である
任意の自然数$ nについて，$ Tが$ \Sigma_{n}健全．
$ \mathcal{N} \models T．
注意1
以降，$ \Gammaは$ \Delta_0, \Sigma_0,\Sigma_1,\dots,\Pi_0,\Pi_1,\dotsのどれかを表しているとする
$ \Sigma_n定義可能性，$ \Pi_n定義可能性
自然数上の$ k項関係$ R \sube \N^kが$ \Gamma定義可能である
自由変数を$ k個持つ$ \Gamma論理式$ \varphi \lbrack v_0,\dots,x_{k-1} \rbrackが存在し，次を満たす．
任意の自然数$ n_0,\dots,n_{k-1} \in \Nについて，
$ (n_0,\dots,n_{k-1}) \in R$ \implies$ \mathcal{N} \models \varphi\lbrack \overline{n_0},\dots,\overline{n_{k-1}} \rbrack
$ Rは$ \Gammaとも略記する．
例
「$ xは偶数である」という1項関係は次の$ \Delta_0論理式で定義される．
$ \exists v_0 \leq x. (x = v_0 + v_0)
（すなわち，偶数の集合は$ \Delta_0である）
$ \Delta_n定義可能性
関係$ Rが$ \Sigma_n定義可能かつ$ \Pi_n定義可能なら，$ \Delta_n定義可能であるという．
定理2
次のことは同値である
$ Rが$ \Delta_1定義可能$ \iff$ Rは計算可能 $ Rが$ \Sigma_1定義可能$ \iff$ Rは計算的枚挙可能 自然数上の$ k項関係$ R \sube \N^k，
自由変数を$ k個持つ論理式$ \varphi \lbrack v_0,\dots,x_{k-1} \rbrackについて，
弱表現
$ Rが，理論$ T上で$ \varphiによって弱表現される 任意の自然数$ n_0,\dots,n_{k-1} \in \Nについて，
$ (n_0,\dots,n_{k-1}) \in R$ \implies$ T \vdash \varphi\lbrack \overline{n_0},\dots,\overline{n_{k-1}} \rbrack
$ Rが理論Tで弱表現される
上を満たす論理式$ \varphiが存在する
(強)表現
$ Rが，理論$ T上で$ \varphiによって(強)表現される
任意の自然数$ n_0,\dots,n_{k-1} \in \Nについて，
$ (n_0,\dots,n_{k-1}) \in R$ \implies$ T \vdash \varphi\lbrack \overline{n_0},\dots,\overline{n_{k-1}} \rbrack
$ (n_0,\dots,n_{k-1}) \notin R$ \implies$ T \vdash \lnot \varphi\lbrack \overline{n_0},\dots,\overline{n_{k-1}} \rbrack
$ Rが理論Tで(強)表現される
上を満たす論理式$ \varphiが存在する
省略
Peano算術$ \mathbf{PA}は$ \mathbf{Q}に数学的帰納法の公理図式を加えて得られる理論である すなわち，$ \mathbf{PA}は加算無限個の公理を持つ．
算術の拡大について
補題2. 拡大補題
$ \mathbf{Q}で証明可能な論理式は，$ \mathbf{Q}の健全な拡大理論でも証明可能．
すなわち，
$ \mathbf{Q} \vdash \varphiのとき，
$ \mathbf{Q}に$ \Sigma_n文$ \psiを付け加えた$ \Sigma_n健全な拡大理論$ \mathbf{Q}' = \mathbf{Q} \cup \{\psi\}でも，$ \mathbf{Q}' \vdash \varphi．
定理3: $ \Sigma_1完全性定理
$ \mathcal{N}で妥当な$ \Sigma_1論理式は，全て$ \mathbf{Q}で証明可能．
すなわち，$ \mathcal{N} \models \varphi$ \implies$ \mathbf{Q}\vdash\varphi
ただし，$ \varphiは$ \Sigma_1論理式
$ Rが$ \Delta_1定義可能
$ \implies$ Rは$ \mathbf{Q}において$ \Sigma_1論理式によって表現可能．
2. $ Rが$ \Sigma_1定義可能かつ，$ Tが$ \mathbf{Q}の$ \Sigma_1健全な拡大理論
$ \implies$ Rを定義する$ \Sigma_1論理式は，$ Rを$ Tにおいて弱表現する．
論理式$ \varphiのGödel数を$ g(\varphi)と表す．
$ g(\varphi)の数項を$ \ulcorner \varphi \urcornerと表す．
すなわち，$ \overline{g(\varphi)} = \ulcorner \varphi\urcorner
論理式の集合$ \Phiの要素$ \varphiのGödel数の集合を$ g(\Phi)と表す．
すなわち，$ g(\Phi) = \{ g(\varphi) \mid \varphi \in \Phi \}
以降，
「論理式のGödel数集合$ g(\Phi)が$ \Gamma定義可能である」を
「論理式の集合$ \Phiが$ \Gamma定義可能」と略記することがある．
理論$ Tが$ \Sigma_1定義可能である，すなわち，$ g(T)が$ \Sigma_1定義可能であるとする．
頑張ると，次の関係が全て$ \Sigma_1定義可能な関係であることがわかる．
$ Tの全ての証明
「$ xは$ Tの証明の一つのGödel数である」
$ Tの全ての定理の集合$ \text{Th}_T = \{ \varphi \mid T \vdash \varphi \}
「$ xは$ Tの定理の一つのGödel数である」
$ \Sigma_1定義可能な理論$ Tに対し
$ Tの全ての定理の集合$ \text{Th}_Tを定義する$ \Sigma_1論理式を$ Tの証明可能性述語と呼ぶ． なお，本来は$ \Sigma_1論理式に限定する必要はない
$ \Sigma_1定義可能な理論$ Tの証明可能性述語$ \text{Pr}_T \lbrack x \rbrackについて，
任意の論理式$ \varphiについて
$ T \vdash \varphi$ \iff$ \mathcal{N} \models \text{Pr}_T \lbrack \ulcorner \varphi \urcorner \rbrack
$ Tが$ \mathbf{Q}の拡大理論とする
$ T \vdash \varphi$ \implies$ T \vdash \text{Pr}_T \lbrack \ulcorner \varphi \urcorner \rbrack
$ T \vdash \text{Pr}_T \lbrack \ulcorner \varphi \urcorner \rbrack$ \implies$ \mathcal{N} \models \text{Pr}_T \lbrack \ulcorner \varphi \urcorner \rbrack
以上より，
$ T \vdash \text{Pr}_T \lbrack \ulcorner \varphi \urcorner \rbrack$ \implies$ T \vdash \varphi
定理4（表現可能性定理）より
$ \text{Th}_Tは$ \Sigma_1定義可能であり，$ Tは$ \mathbf{Q}の$ \Sigma_1健全な拡大理論であるので，
$ \text{Pr}_T \lbrack \ulcorner \varphi \urcorner \rbrackは$ Tにおいて集合$ \text{Th}_Tを弱表現する．
自由変数を一つだけ持つ任意の論理式$ \varphi\lbrack v \rbrackについて，
$ \mathbf{Q} \vdash \psi \leftrightarrow \varphi\lbrack \ulcorner \psi \urcorner \rbrackな，ある文$ \psiが存在する
$ \Gamma \neq \Delta_0のとき，$ \varphi\lbrack v \rbrackが$ \Gamma論理式なら$ \psiも$ \Gamma論理式である．
$ \Sigma_1定義可能かつ，$ \mathbf{Q}の$ \Sigma_1健全な拡大理論$ Tについて，
$ Tの証明可能性述語を$ \text{Pr}_T\lbrack \ulcorner \varphi \urcorner \rbrackとする．
$ \Sigma_1定義可能かつ，$ \mathbf{Q}の$ \Sigma_1健全な拡大理論$ Tについて，
ある$ \Pi_1文$ \varphiが存在して，$ T \not\vdash \varphiかつ$ T \not\vdash \lnot\varphi．
証明
$ \varphiがGödel文であるとする
$ T \vdash \varphiなら
1. $ T \vdash \lnot \text{Pr}_{T}\lbrack\varphi\rbrack （Gödel文の定義）
2. $ T \vdash \lnot \varphi
SnO2WMaN.icon: なぜ？
3. $ T \vdash \varphiかつ$ T \vdash \lnot\varphiは$ Tの無矛盾性に反する．
$ T \vdash \lnot \varphi
1. $ T \vdash \text{Pr}_{T}\lbrack\varphi\rbrack （Gödel文の定義）
1階述語論理であるので，二重否定は肯定になるものとする．
2. $ T \vdash \varphi
3. $ T \vdash \varphiかつ$ T \vdash \lnot\varphiは$ Tの無矛盾性に反する．
よって，$ T \not\vdash \varphiかつ$ T \not\vdash \varphi．
$ \Sigma_1定義可能かつ，$ \mathbf{Q}の無矛盾な拡大理論$ Tについて，
ある$ \Pi_1文$ \varphiが存在して，$ T \not\vdash \varphiかつ$ T \not\vdash \lnot\varphi．
解説
理論の決定不能性
$ \text{Th}^*_Tは$ Tの定理である文の集合であるとする．
すなわち，$ \text{Th}^*_T \sube \text{Th}_Tである．
理論の決定可能性
$ Tは決定可能である
$ \text{Th}^*_Tが$ \Delta_1定義可能である
「$ \text{Th}^*_Tが計算可能である」とも言い換えられる．
理論の決定不能性
$ Tが決定可能でないこと．すなわち$ \text{Th}^*_Tが計算不能であること．
$ Tが本質的に決定不能である
$ Tの無矛盾な拡大理論$ T'で決定可能なものは存在しない．
定理8
$ \mathbf{Q}の無矛盾拡大理論$ Tについて，$ \text{Th}^*_Tを表現する論理式は存在しない．
証明
$ \varphi \lbrack x \rbrackとして存在すると仮定する．
定理5より，$ T \vdash \psi \leftrightarrow \lnot \varphi\lbrack \ulcorner \psi \urcorner \rbrackな，ある文$ \psiが存在する
こうすると
$ T \vdash \psiである（すなわち$ \psiは$ Tの定理である）
$ T \vdash \lnot \varphi\lbrack \ulcorner \psi \urcorner \rbrackである（すなわち$ \psiは$ Tの定理ではない）
よって破綻する．
すなわち，$ \mathbf{Q}の任意の無矛盾拡大理論$ Tについて，$ \text{Th}^*_Tが$ \Delta_1定義可能ではない．
証明
$ \mathbf{Q}の任意の無矛盾拡大理論$ Tについて，$ \text{Th}^*_Tが$ \Delta_1定義可能であると仮定する
$ \text{Th}^*_Tは$ \mathbf{Q}において$ \Sigma_1論理式によって表現可能である
定理4: 表現可能性定理
ところが，定理8よりそのような論理式は存在しない．
$ \mathbf{Q}で表現可能なら当然その拡大である$ Tでも表現可能であるので
よって破綻する．
無矛盾かつ完全な理論$ Tについては
$ \varphi \in \text{Th}^*_T \iff \lnot \varphi \notin \text{Th}^*_Tが成り立つ．
したがって，$ \text{Th}^*_Tが$ \Sigma_1定義可能なら$ \Pi_1定義可能でもある．
よって，$ \text{Th}^*_Tは$ \Delta_1定義可能であり，決定可能である．
ところが，任意の$ \mathbf{Q}の無矛盾拡大理論$ Tについて$ \text{Th}^*_Tは決定不能である(定理9)
よって，無矛盾かつ完全な理論$ Tは存在しないものであることが示される．
SnO2WMaN.icon無矛盾性か完全性のうちなぜ完全性を落として良いのか？はあんまり書いてなかった
定理10
理論$ T + \mathbf{Q}が無矛盾であるような理論$ Tは決定不能である．
証明
理論$ Tについて，
理論$ T' = T + \mathbf{Q}とし，$ T'は無矛盾とする．
$ T'は$ \mathbf{Q}の無矛盾な拡大理論である．
したがって，$ T'は決定不能である．
定理9および本質的決定不能性の定義
$ \bigwedge \mathbf{Q}を$ \mathbf{Q}の8個の公理を$ \landでつなげた文であるとする．
$ T + \mathbf{Q} \vdash \varphi \implies T \vdash \bigwedge \mathbf{Q} \to \varphi
すなわち，決定不能な理論$ T'での証明は$ Tの理論での証明に変換可能である．
このとき，$ Tは$ T'の決定不能性が帰結される．
言語$ \mathscr{L}_Aに関する一階述語論理は決定不能である.
すなわち,$ \text{Th}^*_\emptyset定義不可能である．
$ \text{Th}^*_\emptysetは，一階述語論理の言語$ \mathscr{L}_Aで証明可能な定理の文の集合．
証明
定理10として理論$ T = \emptysetを取ると，
任意の論理式$ \varphiについて$ \emptyset \vdash \bigwedge \mathbf{Q} \to \varphiである．
$ \mathcal{M} \models \mathbf{Q}とすると，全ての文$ \varphiについて$ \mathcal{M} \models \varphi \leftrightarrow \psi\lbrack\ulcorner \varphi \urcorner\rbrackな文$ \psi\lbrack x \rbrackは存在しない．
直感的な説明
$ \mathcal{M}上で，$ \mathcal{M}での文$ \varphiの真偽を定義する論理式$ \psiを構成することはできない．
$ \mathcal{M}の真理定義述語は，$ \mathcal{M}が$ \mathbf{Q}のモデルである以上は定義できない． 証明
1. $ \mathcal{M}が$ \mathbf{Q}のモデルとする
2. $ \text{Th}^*_\mathcal{M} := \{ \varphi \mid \text{$\varphi$ is sentence}, \mathcal{M} \models \varphi\}とする．
3. $ \text{Th}^*_\mathcal{M}は$ \mathbf{Q}の無矛盾で完全な拡大理論である．
4. 3と定理8より
$ \mathbf{Q}の無矛盾拡大理論$ \text{Th}^*_\mathcal{M}について，$ \text{Th}^*_{\text{Th}^*_\mathcal{M}}を表現する論理式は存在しない．
5. $ \text{Th}^*_\mathcal{\text{Th}^*_\mathcal{M}} = \text{Th}^*_\mathcal{M}である
$ \text{Th}^*_\mathcal{\text{Th}^*_\mathcal{M}} := \{ \varphi \mid \text{$\varphi$ is sentence}, \text{Th}^*_\mathcal{M} \vdash \varphi\}
健全性を仮定するなら$ \text{Th}^*_\mathcal{M} \vdash \varphi \implies \mathcal{M}\models\varphi
6. 4と5より，理論$ \text{Th}^*_\mathcal{M}について，$ \text{Th}^*_\mathcal{M}を表現する論理式は存在しない．
定理13
各$ \Gammaに対して次の論理式$ \text{True}_\Gammaが存在する．
$ \Gamma文$ \varphiとし，$ \mathbf{PA} \vdash \varphi \leftrightarrow \text{True}_\Gamma \lbrack \ulcorner \varphi \urcorner\rbrack
論理式$ \text{True}_\Gammaは以下のように現れる．
$ \Gamma = \Delta_0なら$ \Delta_1 \mathbf{PA}論理式として
$ \Gamma \neq \Delta_0なら$ \Gamma論理式として
解説
$ \mathbf{PA}なら，複雑さを$ \Sigma_nまたは$ \Pi_nに制限することで真理定義論理式を取ることができる．